/**
 * @author: lk
 * @data: 2021/11/10 18:18
 */
package LeetCode;

import java.util.concurrent.LinkedTransferQueue;

/**
 * TODO:没写对
 * 两数相加递归版本。最终还是错付了（没写对）。
 */
public class _2 {
    public static void main(String[] args) {
        int[] arr1 = {9, 9, 9, 9, 9, 9, 9};
        int[] arr2 = {9, 9, 9, 9};
        arr1 = new int[]{1, 2, 3, 4};
        arr2 = new int[]{1, 2, 3};
        ListNode l1 = new ListNode(arr1);
        ListNode l2 = new ListNode(arr2);
        ListNode res = new _2().addTwoNumbers(l1, l2);
        System.out.println(res);
        int x = 0;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1, l2, 0);

    }

    /**
     * 依然是“头部对其”版本。
     * @param l1
     * @param l2
     * @param carry
     * @return
     */
    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        System.out.printf("Enter,add %s and %s\n", l1, l2);
        if (l1 == null && l2 == null)
            return null;
        int sum;
        ListNode nextl1,nextl2;
        if (l1 == null) {
            sum = 0 + l2.val + carry;
            nextl1 = null;
            nextl2 = l2.next;
        } else if (l2 == null) {
            sum = 0 + l1.val + carry;
            nextl1 = l1.next;
            nextl2= null;
        }else {
            nextl1 = l1.next;
            nextl2 = l2.next;
            sum = l1.val + l2.val + carry;
        }
        int c= sum/10, s = sum%10;
        ListNode tmp = helper(nextl1,nextl2,c);
        ListNode head = new ListNode(s, tmp);
        System.out.printf("Out,res is %s\n", head);
        return head;

    }

    /**
     * "头部对其"再相加的版本2.这次用了进位位， 是参考别人实现的。但还是错的。
     *
     * @param l1
     * @param l2
     * @param carry
     * @return
     */
    private ListNode helper2(ListNode l1, ListNode l2, int carry) {
        System.out.printf("Enter,add %s and %s\n", l1, l2);
        if (l1 == null && l2 == null)
            return null;
//        else if(l1==null && l2==null)
//            return new ListNode(carry, null);
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        int sum = l1.val + l2.val + carry;
        int s = sum % 10, c = sum / 10;
        ListNode head = new ListNode(s, helper(l1.next, l2.next, c));
        System.out.printf("Out,res is %s\n", head);
        return head;

    }

    /**
     * 这是“头部对其”然后再相加的版本。题意要求的是“尾部对其”然后再相加。
     * 写递归体时，是在考虑所有的情况，即规模为n-1的状态到n的状态中，所有的可能，都要对
     *
     * @param l1
     * @param l2
     * @return
     */
    private ListNode helper1(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        ListNode res = helper1(l1.next, l2.next);
        ListNode tmp = new ListNode(-1, res), head;
        head = tmp;
        int sum = l1.val + l2.val;
        if (sum < 10)
            tmp.val = sum;
        else {
            head = new ListNode(1, tmp);
            tmp.val = sum % 10;
        }
        return head;
    }
}
